All Questions
Tagged with algorithmsbig-o
69 questions
0votes
0answers
87views
What is the Big O notation of modifying an existing element in a heap data structure?
Wikipedia says "increase key" is O(log n) for a binary heap, but it is referring to an internal function. I'm not asking about that: Imagine the data structure had an external/public ...
- 6,824
3votes
1answer
310views
Algorithms: How do I sum O(n) and O(mlog(n)) together?
I'm doing a running time analysis using the aggregate method and I'm a bit confused about what would be the result in this case. I have some intuition in inferring that it would be O(mlog(n)) but I'm ...
- 51
-4votes
1answer
112views
What is the big O of this algorithm? [duplicate]
I think it's O(m*n) but someone said it's O(n). If you think it's O(n) could you provide an explanation? def convert(self, s: str, numRows: int) -> str: if numRows == 1: return ...
- 103
0votes
3answers
754views
Why isn't a counter used to avoid nested for loops for index based operations?
Let's assume we have a method that we want to run as fast as possible and it needs to loop on a 2D array, naturally we would do a nested for loop as such: int[][] arr = new int[3][3]; for(int ...
- 51
0votes
0answers
96views
O(nlogn) + O(logn) =? [duplicate]
So I came upon this time complexity result and I was confused about it, it said that : O(nlogn) + O(logn) =O(log(n+1)) Why is that the case? Shouldn't the result be O(nlogn)?
- 27
0votes
2answers
1kviews
Calculating time complexity of a code snippet
I am trying to calculate the time complexity of the below code snippet def func() { for(i=1; i<=n; i++) { for(j=1; j<=n; j=j+i) { print("hello") } }...
- 111
3votes
1answer
417views
Why the names Omega and Theta in Big Omega and Big Theta?
There was a question asking what the "O" stands for in "Big O", the answer to which seems to be "Ordnung von"/"order of". I wonder what's the origin of the ...
- 791
2votes
1answer
587views
Running time for simple for loops - Big O notation
I am currently doing some exercises with algorithms and I find myself in a huge problem. It seems that everybody understands this type of problem but I have a really hard time figuring it out. For ...
-2votes
2answers
280views
Is looping an array to compare to itself considered O(n^2)? [duplicate]
Often when I'm doing an operation comparing an array to itself, I write code along these lines: function operation (array) { for (let i = 0; i < array.length; i++) { for (let j = i + 1; j <...
- 107
-4votes
1answer
420views
What is the worst case Time Complexity for only the Divide Portion of the Merge Sort Algorithm?
Please, consider the below merge sort algorithm. Here we start with a divide portion which splits the array into halves and we do recursive operation on each half separately. I have ignored the merge ...
2votes
1answer
303views
Big-O Notation and Calculus [closed]
I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
- 129
3votes
3answers
237views
What is the complexity of find and checking prime numbers?
I'm trying to figure out the complexities of these two functions that I've written but could not understand.def First, I thought it is supposed be O(N). But it is not clear how many times the loop ...
- 139
0votes
1answer
768views
Is my reasoning to determine this algorithm's Big-O correct?
Take the following algorithm with two separate sections, and the sections do not influence each other whatsoever (the function is not recursive, as well). void algorithm(int x) { // This section ...
2votes
1answer
470views
Am I allowed to simplify terms while calculating Big O?
I want to calculate the runtime of the following function T(n) = (1+2+3+4+5+...+n)/n At first this doesnt seemed hard to me because it can be solved easily by transforming the formula T(n) = (n(n-1)...
- 131
3votes
3answers
1kviews
randomly filling in empty spaces in a matrix - O(N) amortized time?
Here are two ways to answer the following question. I'm trying to confirm what I believe their time complexity to be: If I had a snake game with a x,y matrix of spaces, some of which were occupied ...
- 182
